package LeetCode;

/**
 * @author BV1Er421K7kF

 * 给你两个字符串，请你在主字符串中找出子字符串的第一个匹配项的下标（下标从0开始）。
 * 如果子串不是主串的一部分，则返回-1。
 * 示例 ：
 * 输入:主串 = "sadbutsad"，子串 = "sad"
 * 输出：0
 * 解释：“sad"在下标0和6处匹配。
 * 第一个匹配项的下标是0，所以返回0。
 */

public class kmpMarch
{
    public static void kmpmarch(String pattern, String main)
    {
        String s = pattern + "#" + main;
        int[] pi = new int[s.length()];
        pi[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            int len = pi[i - 1];
            while (len > 0 && s.charAt(i) != s.charAt(len)) {
                len = pi[len - 1];
            }
            if (s.charAt(i) == s.charAt(len)) {
                len++;
            }
            pi[i] = len;
        }
        for (int i = 0; i < s.length(); i++) {
            if (pi[i] == pattern.length()) {
                System.out.println(i-2*pattern.length());
                System.out.println(main.substring(i-2*pattern.length(), i-pattern.length()));
                break;
            }
        }
    }


    public static void main(String[] args)
    {
        String pattern = "bc";
        String main = "abababcabc";
        kmpmarch(pattern, main);
    }
}

